8.2.2010

• Predpokladejte, ze M je TS s obousmerne nekonecnou paskou. Popiste, jak z M vytvorite TS s jednosmerne nekonecnou paskou, ktery "dela totez" co M. (stacil slovni popis bez instrukci)

• Odvodte, ze funkce faktorial g(x)=x! je primitivne rekurzivni (za predpokladu, ze funkce nasobeni je PRF).

• Popiste 2-aproximacni algoritmus pro obchodniho cestujiciho s trojuhelnikovou nerovnosti, ktery pouziva minimalni kostru. Ukazte, ze skutecne dany algoritmus dosahuje zmineho aprox. pomeru.

• Ukazte, ze problem rozvrhovani je NP-uplny. (soucasti zadani byl popis problemu rozvrhovani z poznamek k cviceni)